题目背景
ZBY 是一只青蛙!
题目描述
如果一只青蛙在 u (u>1) 号荷叶,他会进行一步等概率的跳跃,从 u 号荷叶跳到 1…u 号荷叶。
现在青蛙在 N 号荷叶,求出他跳到 1 号荷叶的期望步数。
输入输出格式
输入格式:
一个正整数 N 。
输出格式:
答案保留 8 位小数。
输入输出样例
输入样例#1:
2
输出样例#1:
2.00000000
输入样例#2:
3
输出样例#2:
2.50000000
样例解释
第一组数据中,三块碎片两两吻合的方案有 1 种,三块碎片中恰好有一对碎片互相吻合的
方案有 3 种,总共有 4 种方案。
第二组数据中,因为第 1、2 块碎片吻合,第 1、3 块碎片冲突,所以第 2、3 块碎片一定
冲突。
说明
对于 10% 的数据,N ≤ 5
对于 20% 的数据,N ≤ 10000
对于 30% 的数据,N ≤ 1000000
对于 100% 的数据,2 ≤ N ≤ 10^18
解题思路
因为青蛙是 zby,所以if(n==1) puts(“0.00000000”);else puts(“1.00000000”);
zbytql!!
感谢北冥咸鱼的倾情讲解。
用 f [ i ] 表示第 i 格到第 1 格的数学期望
理解一下,然后变形
于是可得
两式相减
就这样得出了优秀的 O( n ) 推导式
算下调和级数前缀和就知道啦!
就在欣喜之时,我悄咪咪地瞄到了数据范围
…
https://baike.baidu.com/item/%E8%B0%83%E5%92%8C%E7%BA%A7%E6%95%B0/8019971?fr=aladdin
至于为什么较小的点需要用 O( n ) 递推,因为调和级数前缀和公式是无限逼近的…越大的数误差越小,对于 8 位的精度还是稍微保险一点,那个欧拉常数也可以通过暴算打表推出来
嗯,大概就是这样了
代码
1 |
|